class Solution {
public:
    int px[4] = { 0,1,0,-1 };
    int py[4] = { 1,0,-1,0 };

    vector<int> spiralOrder(vector<vector<int>>& matrix)
    {
        int n = matrix.size();
        int m = matrix[0].size();
        vector<vector<bool>> check(n, vector<bool>(m,false));
        vector<int> ret;

        int x = 0; int y = 0;
        int sum = 0;
        int pos = 0;
        while (1)
        {
            sum++;
            ret.push_back(matrix[x][y]);
            check[x][y] = true;
            if (sum == n * m) return ret;

            int x_next = x + px[pos];
            int y_next = y + py[pos];
            if (x_next >= n || x_next < 0 || y_next >= m || y_next < 0 || check[x_next][y_next])
            {
                //变向
                pos = (++pos) % 4;
                x_next = x + px[pos];
                y_next = y + py[pos];
            }
            x = x_next; y = y_next;
        }
    }
};